package main

import "fmt"

// 如何找出旋转数组的最小元素

func main() {
	arr := []int{5, 6, 1, 2, 3, 4}
	fmt.Println(getMin(arr))
	//arr = []int{1, 1, 0, 1}
	//fmt.Println(getMin(arr))

	// 如何实现旋转数组功能
	rotateArr(arr, 1)
	fmt.Println(arr)
}

func getMin(arr []int) int {
	if arr == nil {
		return -1
	} else {
		return getMinPara(arr, 0, len(arr)-1)
	}
}

func getMinPara(arr []int, low, high int) int {
	if high < low {
		return arr[0]
	}

	if high == low {
		return arr[low]
	}

	mid := low + ((high - low) >> 1)

	if arr[mid] < arr[mid-1] {
		return arr[mid]
	} else if arr[mid+1] < arr[mid] {
		return arr[mid+1]
	} else if arr[high] > arr[mid] {
		return getMinPara(arr, low, mid-1)
	} else if arr[mid] > arr[low] {
		return getMinPara(arr, mid+1, high)
	} else {
		left := getMinPara(arr, low, mid-1)
		right := getMinPara(arr, low, mid-1)
		if left < right {
			return left
		} else {
			return right
		}
	}
}

func rotateArr(arr []int, div int) {
	if arr == nil || div <= 0 || div >= len(arr)-1 {
		return
	}

	swap(arr, 0, div)
	swap(arr, div+1, len(arr)-1)
	swap(arr, 0, len(arr)-1)
}

func swap(arr []int, low, high int) {
	for ; low < high; low, high = low+1, high-1 {
		arr[low], arr[high] = arr[high], arr[low]
	}
}
